package Leetcode第一期;

/**
 * @author : K k
 * @date : 9:29 2020/9/15
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: [7,5,6,4]
 * 输出: 5
 */
public class 数组中的逆序对_51 {

    //先排序再计算
    public int reversePairs(int[] nums) {
        int len = nums.length;
        int count = 0;
        //归并排序
        int[] copy = new int[len];
        for (int i = 0; i < len; i++) {
            copy[i] = nums[i];
        }
        int[] temp = new int[len];
        count=mergeSort(copy, 0, nums.length-1, temp);
        return count;
    }

    private int mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int leftCount = mergeSort(nums, left, mid, temp);
        int rightCount = mergeSort(nums, mid + 1, right, temp);

        if (nums[mid] <= nums[mid + 1]) {
            //这个判断 说明分组两边都已经排好序 只需要直接拼接数组即可
            return leftCount + rightCount;
        }
        int crossCount = merge(nums, left, mid, right, temp);

        return crossCount + leftCount + rightCount;
    }

    private int merge(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        int leftBegin = left;
        int rightBegin = mid + 1;
        int count = 0;

        for (int i = left; i <= right; i++) {
            //作为零时数组的索引
            if (leftBegin == mid + 1) {
                nums[i] = temp[rightBegin++];
            } else if (rightBegin == right + 1) {
                nums[i] = temp[leftBegin++];
            } else if (temp[leftBegin] > temp[rightBegin]) {
                nums[i] = temp[rightBegin++];
                count+=(mid-leftBegin)+1; //遇到逆序加1
            } else {
                nums[i] = temp[leftBegin++];
            }
        }
        return count;
    }

    /*private void quickSort(int[] nums, int left, int right) {
        if (left<right){
            int mid=getMiddle(nums,left,right);
            quickSort(nums,left,mid-1);
            quickSort(nums,mid+1,right);
        }
    }

    private int getMiddle(int[] nums, int left, int right) {
        //基准值
        int temp=nums[left];
        while(left<right){
            while (left<right && nums[right]<=temp){
                right--;
            }
            nums[left]=nums[right];
            while (left<right && nums[left]>=temp){
                left++;
            }
            nums[right]=nums[left];
        }
        nums[left]=temp;
        return left;
    }*/

    public static void main(String[] args) {
        数组中的逆序对_51 x=new 数组中的逆序对_51();
        System.out.println(x.reversePairs(new int[]{7, 5, 6, 4}));
    }
}
